{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Insert into a Binary Search Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #binary-search-tree #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #二叉搜索树 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: insertIntoBST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉搜索树中的插入操作"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定二叉搜索树（BST）的根节点<meta charset=\"UTF-8\" />&nbsp;<code>root</code>&nbsp;和要插入树中的值<meta charset=\"UTF-8\" />&nbsp;<code>value</code>&nbsp;，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 <strong>保证</strong> ，新值和原始二叉搜索树中的任意节点值都不同。</p>\n",
    "\n",
    "<p><strong>注意</strong>，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 <strong>任意有效的结果</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/05/insertbst.jpg\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [4,2,7,1,3], val = 5\n",
    "<strong>输出：</strong>[4,2,7,1,3,5]\n",
    "<strong>解释：</strong>另一个满足题目要求可以通过的树是：\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/05/bst.jpg\" />\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [40,20,60,10,30,50,70], val = 25\n",
    "<strong>输出：</strong>[40,20,60,10,30,50,70,null,null,25]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [4,2,7,1,3,null,null,null,null,null,null], val = 5\n",
    "<strong>输出：</strong>[4,2,7,1,3,5]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中的节点数将在<meta charset=\"UTF-8\" />&nbsp;<code>[0,&nbsp;10<sup>4</sup>]</code>的范围内。<meta charset=\"UTF-8\" /></li>\n",
    "\t<li><code>-10<sup>8</sup>&nbsp;&lt;= Node.val &lt;= 10<sup>8</sup></code></li>\n",
    "\t<li>所有值&nbsp;<meta charset=\"UTF-8\" /><code>Node.val</code>&nbsp;是&nbsp;<strong>独一无二</strong>&nbsp;的。</li>\n",
    "\t<li><code>-10<sup>8</sup>&nbsp;&lt;= val &lt;= 10<sup>8</sup></code></li>\n",
    "\t<li><strong>保证</strong>&nbsp;<code>val</code>&nbsp;在原始BST中不存在。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [insert-into-a-binary-search-tree](https://leetcode.cn/problems/insert-into-a-binary-search-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [insert-into-a-binary-search-tree](https://leetcode.cn/problems/insert-into-a-binary-search-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,7,1,3]\\n5', '[40,20,60,10,30,50,70]\\n25', '[4,2,7,1,3,null,null,null,null,null,null]\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def helper(self, root: TreeNode, val: int) -> TreeNode:\n",
    "        if root==None:\n",
    "            return TreeNode(val)\n",
    "        if root.val < val:\n",
    "            root.right = self.helper(root.right, val)\n",
    "        else:\n",
    "            root.left = self.helper(root.left, val)\n",
    "        return root\n",
    "        \n",
    "    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:\n",
    "        return self.helper(root, val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def insertIntoBST(self, root, val):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type val: int\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "#       if root == None :\n",
    "        if not root:\n",
    "            return TreeNode(val)\n",
    "        if val > root.val:\n",
    "            root.right = self.insertIntoBST(root.right, val)\n",
    "        if val < root.val:\n",
    "            root.left = self.insertIntoBST(root.left, val)\n",
    "        return root\n",
    "#--------------------- \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def insertIntoBST(self, root, val):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type val: int\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        res = root\n",
    "        temp = 0\n",
    "        if root == None:\n",
    "            res.val = val \n",
    "            return res\n",
    "        while root:\n",
    "            print(root)\n",
    "            if root.val > val:\n",
    "                temp = root\n",
    "                root = root.left\n",
    "            elif root.val < val:\n",
    "                temp = root\n",
    "                root = root.right\n",
    "        if temp.val > val:\n",
    "            temp.left = TreeNode(val)\n",
    "        else:\n",
    "            temp.right = TreeNode(val)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def insertIntoBST(self, root: 'TreeNode', val: 'int') -> 'TreeNode':\n",
    "        \n",
    "        \n",
    "        if root.val<val:\n",
    "            if root.right:\n",
    "                self.insertIntoBST(root.right,val)\n",
    "            else:\n",
    "                root.right=TreeNode(val)\n",
    "        if root.val>val:\n",
    "            if root.left:\n",
    "                self.insertIntoBST(root.left,val)\n",
    "            else:\n",
    "                root.left=TreeNode(val)\n",
    "        return root\n",
    "            \n",
    "                \n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def insertIntoBST(self, root, val):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type val: int\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if root:\n",
    "            if val < root.val:\n",
    "                root.left = self.insertIntoBST(root.left, val)\n",
    "            else:\n",
    "                root.right = self.insertIntoBST(root.right, val)\n",
    "            return root\n",
    "        return TreeNode(val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def insertIntoBST(self, root, val):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type val: int\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if root == None:\n",
    "            return TreeNode(val)\n",
    "        elif root.val > val:\n",
    "            print(root.val)\n",
    "            root.left = self.insertIntoBST(root.left, val)\n",
    "        elif root.val <= val:\n",
    "            root.right = self.insertIntoBST(root.right, val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:\n",
    "        \n",
    "        def dfs(node):\n",
    "            if node == None:\n",
    "                return\n",
    "\n",
    "            if node.val > val:\n",
    "                if node.left == None:\n",
    "                    node.left = TreeNode(val)\n",
    "                    return\n",
    "                dfs(node.left)\n",
    "            else:\n",
    "                if node.right == None:\n",
    "                    node.right = TreeNode(val)\n",
    "                    return\n",
    "                dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:\n",
    "        node = root\n",
    "        if root is None:\n",
    "            return TreeNode(val)\n",
    "        while True:\n",
    "            if val < node.val:\n",
    "                if node.left is None:\n",
    "                    node.left = TreeNode(val)\n",
    "                    return root\n",
    "                else:\n",
    "                    node = node.left\n",
    "            else:\n",
    "                if node.right is None:\n",
    "                    node.right = TreeNode(val)\n",
    "                    return root\n",
    "                else:\n",
    "                    node = node.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:\n",
    "        \"\"\"\n",
    "        注意: 插入的节点一定是叶子节点\n",
    "        \"\"\"\n",
    "        if root is None:\n",
    "            # 如果根节点为空 直接让root指向新创建的节点\n",
    "            root = TreeNode(val)\n",
    "            return root\n",
    "        \n",
    "        curr = root\n",
    "        parent = curr\n",
    "        # 寻找val的父节点\n",
    "        while curr is not None:\n",
    "            # 记录比较结果 下面要用到\n",
    "            cmp = val - curr.val\n",
    "            parent = curr\n",
    "            if cmp > 0:\n",
    "                # val 大于当前节点的值 往curr的右子节点找\n",
    "                curr = curr.right\n",
    "            elif cmp < 0:\n",
    "                # val小于当前节点的值 往curr的右子节点找\n",
    "                curr = curr.left\n",
    "            else:\n",
    "                # 如果相等 直接覆盖 当然也可以不做任何处理 可以直接返回root\n",
    "                curr.val = val\n",
    "                return root\n",
    "            \n",
    "        node = TreeNode(val)\n",
    "        # 根据cmp比较结果设置左或者右子节点\n",
    "        if cmp > 0:\n",
    "            parent.right = node\n",
    "        else:\n",
    "            parent.left = node\n",
    "            \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:\n",
    "\n",
    "        def insert(root, val):\n",
    "            if not root:\n",
    "                root = TreeNode(val)\n",
    "                return root\n",
    "            \n",
    "            if val < root.val:\n",
    "                root.left = insert(root.left, val)\n",
    "            elif val > root.val:\n",
    "                root.right = insert(root.right, val)\n",
    "            return root\n",
    "        \n",
    "        return insert(root, val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:\n",
    "        if root is None:\n",
    "            return TreeNode(val)\n",
    "        p, node = root, TreeNode(val) \n",
    "        while p is not None:\n",
    "            if p.val > val:\n",
    "                if p.left is not None:\n",
    "                    p = p.left\n",
    "                else:\n",
    "                    p.left = node \n",
    "                    return root\n",
    "            else:\n",
    "                if p.right is not None:\n",
    "                    p = p.right\n",
    "                else:\n",
    "                    p.right = node \n",
    "                    return root \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:\n",
    "        # 这题咋这么简单，第一次提交node.val > val忘写.val了，第二次过\n",
    "        # 74.26% 5.04%\n",
    "        if not root:\n",
    "            return TreeNode(val)\n",
    "        \n",
    "        node = root\n",
    "\n",
    "        while node:\n",
    "            if node.val > val:\n",
    "                if not node.left:\n",
    "                    node.left = TreeNode(val)\n",
    "                    break\n",
    "                else:\n",
    "                    node = node.left\n",
    "                    continue\n",
    "            else:\n",
    "                if not node.right:\n",
    "                    node.right = TreeNode(val)\n",
    "                    break\n",
    "                else:\n",
    "                    node = node.right\n",
    "                    continue\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:\n",
    "        if not root:\n",
    "            return TreeNode(val)\n",
    "        node = root\n",
    "        while node:\n",
    "            if val < node.val:\n",
    "                if not node.left:\n",
    "                    node.left = TreeNode(val)\n",
    "                    break\n",
    "                else:\n",
    "                    node = node.left\n",
    "            else:\n",
    "                if not node.right:\n",
    "                    node.right = TreeNode(val)\n",
    "                    break\n",
    "                else:\n",
    "                    node = node.right\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:  # 递归解决\n",
    "        if root is None:  # 如果当前节点为空，则在这个地方插入指定节点\n",
    "            root = TreeNode()  # 新建一个节点\n",
    "            root.val = val  # 节点赋值\n",
    "            return root  # 返回新建的节点\n",
    "        elif val < root.val:  # 如果插入的值小于当前节点的值\n",
    "            root.left = self.insertIntoBST(root.left, val)  # 则在当前节点的左子树中插入\n",
    "        else:\n",
    "            root.right = self.insertIntoBST(root.right, val)  # 否则在当前节点的右子树中中插入\n",
    "        return root  # 返回\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:  # 非递归解决\n",
    "#         if root is None:  # 如果当前节点为空，则在这个地方插入指定节点\n",
    "#             root = TreeNode(val=val)  # 新建一个节点\n",
    "#             return root  # 返回新建的节点\n",
    "#         node = root  # 记根节点为当前节点\n",
    "#         while node:  # 如果当前节点不为空\n",
    "#             pre = node  # 记录当前节点，用于后续的连接操作\n",
    "#             if val < node.val:  # 如果插入的值小于当前节点的值\n",
    "#                 node = node.left  # 当前节点向左子树转移\n",
    "#             elif val > node.val: \n",
    "#                 node = node.right  # 否则当前节点向右子树转移\n",
    "#         new_node = TreeNode(val=val)  # 循环结束，说明已经到了底部，新建节点并赋值\n",
    "#         if val < pre.val:  # 根据插入的值与父节点值的大小，决定插入到父节点的左右子树上\n",
    "#             pre.left = new_node\n",
    "#         else:\n",
    "#             pre.right = new_node\n",
    "#         return root  # 返回根节点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:\n",
    "        if root is None:\n",
    "            return TreeNode(val)\n",
    "        if root.val > val:\n",
    "            root.left = self.insertIntoBST(root.left, val)\n",
    "        else:\n",
    "            root.right = self.insertIntoBST(root.right, val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:\n",
    "        if not root:\n",
    "            return TreeNode(val)\n",
    "        root1=TreeNode(root.val)\n",
    "        def port(node,node1):\n",
    "            if node.left!=None:\n",
    "                node1.left=TreeNode(node.left.val)\n",
    "                port(node.left,node1.left)\n",
    "            if node.right!=None:\n",
    "                node1.right=TreeNode(node.right.val)\n",
    "                port(node.right,node1.right)             \n",
    "        port(root,root1)\n",
    "        def f(node):\n",
    "            if node.val>val:\n",
    "                if node.left:\n",
    "                    f(node.left)\n",
    "                else:\n",
    "                    node.left=TreeNode(val)\n",
    "                    return\n",
    "            elif node.val<val:\n",
    "                if node.right:\n",
    "                    f(node.right)\n",
    "                else:\n",
    "                    node.right=TreeNode(val)\n",
    "                    return\n",
    "        f(root1)\n",
    "        return root1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return TreeNode(val)\n",
    "        if root.val < val:\n",
    "            root.right = self.insertIntoBST(root.right, val)\n",
    "        elif root.val > val:\n",
    "            root.left = self.insertIntoBST(root.left, val)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return TreeNode(val)\n",
    "        \n",
    "        pos = root\n",
    "        while pos:\n",
    "            if val < pos.val:\n",
    "                if not pos.left:\n",
    "                    pos.left = TreeNode(val)\n",
    "                    break\n",
    "                else:\n",
    "                    pos = pos.left\n",
    "            else:\n",
    "                if not pos.right:\n",
    "                    pos.right = TreeNode(val)\n",
    "                    break\n",
    "                else:\n",
    "                    pos = pos.right\n",
    "        \n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return TreeNode(val=val)\n",
    "        point=root\n",
    "        while True:\n",
    "            if val<point.val:\n",
    "                if point.left:\n",
    "                    point=point.left\n",
    "                else:\n",
    "                    point.left=TreeNode(val=val)\n",
    "                    return root\n",
    "            elif val>point.val:\n",
    "                if point.right:\n",
    "                    point=point.right\n",
    "                else:\n",
    "                    point.right=TreeNode(val=val)\n",
    "                    return root\n",
    "        return root\n",
    "                \n",
    "       \n",
    "        \n",
    "            \n",
    "      \n",
    "      \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        def findplace(root: TreeNode, val: int):\n",
    "            if not root:\n",
    "                root = TreeNode()\n",
    "                root.val = val\n",
    "                return root\n",
    "            if root.val > val and root.left:\n",
    "                findplace(root.left, val)\n",
    "            if root.val > val and not root.left:\n",
    "                root.left = findplace(root.left, val)\n",
    "            if root.val < val and root.right:\n",
    "                findplace(root.right, val)\n",
    "            if root.val < val and not root.right:\n",
    "                root.right = findplace(root.right, val)\n",
    "        if root:\n",
    "            findplace(root, val)\n",
    "        else:\n",
    "            root = TreeNode()\n",
    "            root.val = val\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "\n",
    "        def dfs(root, val):\n",
    "            print(root)\n",
    "            if root.left and root.left.val < val < root.val:\n",
    "                if root.left.right:\n",
    "                    dfs(root.left, val)\n",
    "                else:\n",
    "                    tmp = root.left\n",
    "                    root.left = TreeNode(val)\n",
    "                    root.left.left = tmp\n",
    "                return\n",
    "            elif not root.left and val < root.val:\n",
    "                root.left = TreeNode(val)\n",
    "                return\n",
    "            elif val < root.val:\n",
    "                dfs(root.left, val)\n",
    "            elif root.right and root.val < val < root.right.val:\n",
    "                if root.right.left:\n",
    "                    dfs(root.right, val)\n",
    "                else:\n",
    "                    tmp = root.right\n",
    "                    root.right = TreeNode(val)\n",
    "                    root.right.right = tmp\n",
    "                return\n",
    "            elif not root.right and val > root.val:\n",
    "                root.right = TreeNode(val)\n",
    "                return\n",
    "            else:\n",
    "                dfs(root.right, val)\n",
    "            \n",
    "\n",
    "        if not root:\n",
    "            return TreeNode(val)\n",
    "        dfs(root, val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "            new = TreeNode(val)\n",
    "            if not root: #遇到空节点，返回一个新的节点\n",
    "                return new\n",
    "            elif not root.left and root.val > val: #否则若没有左孩子 并且val 小于 rootroot，插入到左孩子\n",
    "                root.left = new\n",
    "            elif not root.right and root.val<val: #同上\n",
    "                root.right = new\n",
    "\n",
    "            if val>root.val:\n",
    "                self.insertIntoBST(root.right, val)\n",
    "            if val < root.val :\n",
    "                self.insertIntoBST(root.left, val)\n",
    "            print(root)\n",
    "            return root\n",
    "        \n",
    "        # return insert(cur,val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        newNode = TreeNode(val)\n",
    "        if not root: return newNode\n",
    "        if not root.left and val < root.val:\n",
    "            root.left = newNode\n",
    "        if not root.right and val > root.val:\n",
    "            root.right = newNode\n",
    "        if val < root.val:\n",
    "            self.insertIntoBST(root.left, val)\n",
    "        if val > root.val:\n",
    "            self.insertIntoBST(root.right, val)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:\n",
    "\n",
    "        if root == None:  # 公司里没人，直接当老大，返回走人\n",
    "            return TreeNode(val)\n",
    "\n",
    "        def DangDidi(root, baba, val):\n",
    "\n",
    "            if root == None:  # 找到自己所属的爸爸了。\n",
    "                if val < baba.val:  # 小就站左边。\n",
    "                    baba.left = TreeNode(val)\n",
    "                else:  # 大就站右边。\n",
    "                    baba.right = TreeNode(val)\n",
    "                return\n",
    "\n",
    "            if val < root.val:  # 小就往左找。\n",
    "                DangDidi(root.left, root, val)\n",
    "            else:  # 大就往右找。\n",
    "                DangDidi(root.right, root, val)\n",
    "\n",
    "        DangDidi(root, None, val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return TreeNode(val)\n",
    "        \n",
    "        if root.val > val:\n",
    "            root.left = self.insertIntoBST(root.left, val)\n",
    "        elif root.val < val:\n",
    "            root.right = self.insertIntoBST(root.right, val)\n",
    "        \n",
    "        return root"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
